package q88_merge;

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] n1 = new int[]{0};
        int[] n2 = new int[]{1};
        s.merge(n1, 0, n2, 1);
        System.out.println(Arrays.toString(n1));

    }

    /**
     * 此题控制空间复杂度的核心在于：
     * 直接对排好序的数组最后元素进行比较，这样就能直接决定数组最后的数
     * 也就实现了nums1的原地修改
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (m == 0){
            for (int i = 0; i < nums2.length; i++) {
                nums1[i] = nums2[i];
            }
            return;
        }

        int l1 = m - 1, l2 = n - 1;// 两个指针分别指向数组最后
        int l = nums1.length - 1;// 最大数的指针
        while (l2 >= 0) {

            if (nums1[l1] > nums2[l2] && l > l2){
                nums1[l] = nums1[l1];
                nums1[l1] = 0;
                l1 = Math.max(l1 - 1, 0);
                l--;
            }else {
                nums1[l] = nums2[l2];
                l2--;
                l--;
                }
            }
        }


}
